The present invention relates to authentication.
Many mechanisms have been developed in order to authenticate a first party with a second party. These mechanisms are often based on key cryptography.
A “key” is a data sequence that can be used in an encryption/decryption (or ciphering/deciphering) algorithm to protect certain security sensitive information. A sender encrypts data with a key based encryption function, and sends it over an interface, to a recipient. The recipient decrypts the data received with a key based decryption function. So-called “symmetric cryptography” involves algorithms in which the key used for encryption is identical to the key used for decryption. By contrast, so-called “asymmetric cryptography” involves algorithms in which the key used for encryption is not necessarily identical to the key used for decryption, but rather interdependent through a mathematical relationship, both keys forming an “asymmetrical key pair”.
Asymmetrical key pairs often comprise a “public” key used in conjunction with a “private” key. The “public” key, usually a long data sequence, is shared with a variety of systems, whereas the “private” key is not disseminated. For some key pairs, the public key is computed using the private key and a mathematical relation (such as the digital logarithm), which is such that it is virtually impossible to derive the private key from the public one.
FIG. 1 shows an example where a first party A (1) is authenticated with a second party B (2) by virtue of symmetric cryptography. A has secret information in the form of a private key k, also known by B. This key k is kept private and is unknown to unauthorized parties. B first sends a random number x to A (transmission 4). A ciphers it with use of his private key k, in order to obtain a ciphered number Ek(x) which is sent to B (transmission 5). Then, B deciphers the received number with use of the key k (reference 6). The deciphering is achieved with a k-based function Dk, reverse to the ciphering function. The result of this deciphering is compared to the initial number x by B. If Dk(Ek(x)) equals x, it means that A has ciphered the number x with the correct private key k. Since only A and B know this key, this authenticates A with B. If, by contrast, Dk(Ek(x)) is different from x, it may mean that A has ciphered the number x with an incorrect key, and thus A may be an usurper.
FIG. 2 shows another example of a symmetric authentication mechanism, in which the same operations as in FIG. 1 are distributed between A, B and a trusted third party TTP 3. In this example, B does not hold the private key k of A. Only the TTP 3 does. B first sends a random number x to A (transmission 7). A ciphers it with his private key k, in order to obtain a ciphered number Ek(x) which is sent to B (transmission 8). B forwards the received number to the TTP 3 (transmission 9), which deciphers it with the function Dk reverse to the ciphering function Ek, thanks to his knowledge of the private key k. The result of the deciphering is sent to B (transmission 10), where a comparison between Dk(Ek(x)) and x can be made (reference 11). Like in the case of FIG. 1, A is authenticated with B only when the comparison is positive.
The ANSI (American National Standards Institute) standard DES (Data Encryption Standard) as well as the NIST (National Institute of standards and Technology) standard AES (Advanced Encryption Standard) are well known encryption algorithms which can be used in such symmetric authentication mechanisms.
In other examples using asymmetric cryptography, the parties are provided with dual keys, such that the number ciphered by the first party with the first key can be deciphered by the second party with the second key dual to the first key.
FIG. 3 shows an example of an authentication mechanism using asymmetric cryptography. In this example, a first party A (1) has secret information in the form of a private key k for ciphering data. This key k is kept private and is unknown to unauthorized parties. A also has a public key K that another party can use for deciphering data received from A. In order to ensure that B is provided with the correct public key K in view of an authentication of A, A sends B a certificate containing his key K (transmission 12).
A's certificate Cert(A) can advantageously be built by a certification authority and can have the form specified in the ITU-T (International Telecommunication Union) standard X.509 and schematically shown in FIG. 4 (reference 16). It is divided into two different parts. The information part 17 includes the public key K of A. It also includes information such as an identity of the certification authority, A's name, some validity information like the expiry date of the certificate, as well as an algorithm used by the certification authority to sign the certificate. The other part 18 contains the signature (thumbprint) of the certificate obtained with the algorithm indicated in the information part 17. The signature is generally obtained by applying a hash algorithm to the information part 17 of the certificate, whose result is ciphered with a private key of the certification authority. The hash algorithm can be SHA-1 (specified in the “Secure Hash Signature Standard (SHS)” by the NIST (see FIPS PUB 180-2)) or a message-digest algorithm such as MD2, MD4 or MD5 (further information the message-digest algorithms can be found in the Request For Comments 1319-121 published by the Internet Engineering Task Force (IETF))
On reception of Cert(A), B calculates a hash of the information part 17 of the certificate with the hash function corresponding to the algorithm indicated in the Cert(A). It also deciphers the signature part 18 of the certificate by using the public key of the certification authority, and thus obtains the corresponding hash. If both hash values are equal, Cert(A) is valid and the public key K of A is reliable.
B sends a random number x to A (transmission 13). A ciphers it with his private key k, in order to obtain a ciphered number Ek(X) which is sent to B (transmission 14). Then, B deciphers the received number with the public key K of A (reference 15). The deciphering uses a K-based function DK reverse to the ciphering function Ek. The result of this deciphering is compared to the initial number x by B. If DK(Ek(x)) equals x, it means that A has ciphered the number x with the correct private key k. Since, only A knows this key, this authenticates A with B. If, by contrast, DK(Ek(x)) is different from x, it may mean that A has ciphered the number x with an incorrect key, and thus A may be an usurper.
For example, the widely used RSA cryptosystem, described by R. L. Rivest, A. Shamir and L. Adleman in the article “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM 21 (1978), p. 120-126, can be used in such asymmetric authentication.
Like in the case of FIG. 2, a trusted third, party TTP could be in charge of deciphering and potentially of the validity check of A's certificate. This allows B to have light data processing means.
In the mechanisms described above, information relating to A is revealed to B. Indeed, in the example of FIG. 1, a random number x known by B and ciphered with A's private key k is sent to B. Since B also knows A's private key, he is in a position to prove that A has been authenticated with him. The same applies to the example of FIG. 3: a random number x known by B and ciphered with A's private key k is sent to B. Since B is capable of retrieving x from the received ciphered number with A's public key, he is in a position to prove that A has been authenticated with him.
Such authentication mode is said to be opposable in the following, since B can oppose his authentication to A, by proving to a third party that A has been authenticated with him.
In a number of applications, such opposability towards the authenticated party is undesirable, in order to protect his privacy. In other terms, the authenticating party must have a sufficient degree of certainty that the authenticated party is the one he claims to be; but he must not be in a position to keep information which could later prove that the authenticated party has been authenticated with him.
Known authentication mechanisms reach this goal, i.e. can operate in a non-opposable mode. This is especially the case for mechanisms of the zero knowledge type.
FIG. 5 shows an example of such mechanism. A first party A (21) has secret information in the form of a secret number r. A also has a public identity ld which is a function of the secret number r, i.e. ld=f(r). For instance, f is a function such as f(a.b)=f(a).f(b), for any numbers a and b. It must be chosen in such a way that its reverse function f−1 is very difficult to calculate. For example, f could a square function modulo an integer n. The function f is known by the second party B (22) At the beginning of the authentication, A chooses a random number y, calculates z=f(y) and sends it to the second party B (transmission 23). B can then send A either a “0” (transmission 24) for asking for f−1(z) or a “1” (transmission 27) for asking for f−1(z.ld), that is f−1(z).r. A responds to the reception of a “0” with the value y (transmission 25). On reception, B calculates f(y) and can check that it is equal to the previously received value z (reference 26). Alternatively, A responds to the reception of a “1” with the value y.r (transmission 28). On reception, B calculates f(y.r)=f(y).f(r) and checks whether it is equal to z.ld (reference 29). In case of equality, this means that A knows the secret number r and thus is the one he claims to be. Therefore, A is authenticated with B.
The reason why B randomly sends a “0” or a “1” to A is to avoid cheating from A. Indeed, if A was always supposed to send f−1(z.ld) to B, he could send z/ld instead of z in the initial transmission 23. Then, f−1(z.ld) would be replaced by f−1(z)=y, which does not need any knowledge of the secret number r from A. Since A does not know in advance whether he will receive a “0” or a “1” , he cannot cheat. If A always sends a correct response to the “0s” or “1s” sent by B for a number k of successive uses of the mechanism, it means that A indeed holds the secret number r. Therefore, A is authenticated with B.
It must noted that in the example of FIG. 5, B knows that A has been authenticated with him (when a “1” has been sent to A) because he verifies that f(y.r) is proportional to A's identity ld by the random number z previously received. But, he is not in a position to prove it. Indeed, it could be shown that, since B can choose in advance which sequence of “0s” and “1s” he will use, he could invent an imaginary successful dialog with another fictive party, and wrongly claim on the basis of this dialog that the fictive party has A's identity and thus that A has been authenticated with him.
In other words, the authentication mechanism of FIG. 3, whereas it is efficient, does not allow B to prove that A has been authenticated with him. Such authentication is thus not opposable to A. A's privacy is thus protected in this regard.
The Fiat-Shamir algorithm, described in the article “How to prove yourself; practical solutions to identification and signature problems”, CRYPTO 86, Springer-Verlag 1987, p. 186-194, is an example of a zero knowledge authentication mechanism consistent with what has been described above.
However, even when a party wishes to be authenticated with a non-opposable authentication method, it is not certain that the authenticating party supports such mechanism or accepts this mode of operation. This difficulty may prevent the parties to carry out an access or a service (e.g. a communication service, a commercial transaction, an information exchange, etc.), since no authentication has been possible previously.
Moreover, even if the zero knowledge mechanism improves the level of A's privacy protection, by preventing B from proving that A has been authenticated with him, it could considered as insufficient in some cases. For instance, there are applications in which not only the authentication should not be opposable, but also the identity of the authenticated party should not be revealed.
But, in the authentication mode described above, B is always capable of determining that A has been authenticated with him. For instance, in the example of FIG. 1, B must know that A is the one trying to authenticate himself, to be in a position to decipher the received number Ek(x). Indeed, such deciphering is based on the use by B of A's private key k. Similarly, in the example of FIG. 3, B must know that A is trying to authenticate himself to be in a position to decipher the received number Ek(x) by using A's public key K. Even in the example of FIG. 5, B knows A's identity ld, since he uses it to check that f(y.r)=z.ld.
Therefore, A's privacy is not totally protected in this non-anonymous authentication mode, even when using a non-opposable authentication mechanism.
An object of the present invention is to limit the above-mentioned disadvantages.
Another object of the invention is to allow authentication taking into account the protection of privacy.
Another object of the invention is to allow authentication for different policies and capabilities of the parties involved in terms of protection of privacy.